package com.yahoo.labs.snow.solver;

import it.unimi.dsi.fastutil.ints.IntOpenHashSet;

import java.util.Vector;

import com.yahoo.labs.cluster.Clustering;
import com.yahoo.labs.snow.ProblemInstance;
import com.yahoo.labs.snow.Snowflake;

/**
 * Cluster the nodes, then for each cluster picks the best possible snowflake in that cluster.
 * 
 * @author chato
 *
 */
public class ClusterAndPickSolver extends Solver {

	public ClusterAndPickSolver(ProblemInstance problem) {
		super(problem);
	}

	@Override
	public Vector<Snowflake> solve(int numSnowflakes) {
		if (problem.numNodes() < numSnowflakes) {
			throw new IllegalArgumentException("Too few nodes");
		}

		logger.info("Running clustering");
		int[] clustering = Clustering.symmetrizeAndCluster(problem.getCompat(), numSnowflakes);
		if (clustering.length != problem.numNodes()) {
			throw new IllegalStateException("Wrong length of returned clustering");
		}

		IntOpenHashSet clusterIds = new IntOpenHashSet();
		for (int clusterNum : clustering) {
			clusterIds.add(clusterNum);
		}
		logger.info("Number of clusters: " + clusterIds.size());

		Vector<Snowflake> solution = new Vector<Snowflake>();

		for (int clusterId : clusterIds) {
			IntOpenHashSet clusterMembers = new IntOpenHashSet();
			for (int node = 0; node < clustering.length; node++) {
				if (clustering[node] == clusterId) {
					clusterMembers.add(node);
				}
			}
			logger.info("Members of cluster " + clusterId + ": " + clusterMembers);

			Snowflake bestFlake = bestFlake(clusterMembers);

			solution.add(bestFlake);

		}

		return solution;
	}

	/**
	 * Finds a good snowflake inside a cluster, by exhaustively checking for each of its members
	 * what is the quality of the snowflake with that member as its center, using {@link #pickFlake}.
	 * 
	 * @param clusterMembers the members of a cluster
	 * @return the snowflake picked
	 */
	private Snowflake bestFlake(IntOpenHashSet clusterMembers) {
		double bestScore = -1.0;
		Snowflake bestSnowflake = null;

		for (int center : clusterMembers) {
			Snowflake snowflake = pickFlake(center, clusterMembers);
			double score = snowflake.getSumIntraCompat();
			if (score > bestScore) {
				bestScore = score;
				bestSnowflake = snowflake;
			}
		}
		return bestSnowflake;
	}
}
